#include <vector>
#include <algorithm>
#include <limits>
#include <iostream>
#include "conio.h"

using namespace std;

double knapasck_problem_rec(int max_weight, const vector<bool> &available_items, const vector<int> &weights, 
	const vector<int> &values)
{	
	double max_revenue = numeric_limits<double>::min();
	bool can_put_something = false;

	for (int i_item = 0; i_item < available_items.size(); ++i_item)
	{
		if (available_items[i_item] && weights[i_item] <= max_weight)
		{
			vector<bool> changed_availability = available_items;
			changed_availability[i_item] = 0;
			double cur_revenue = weights[i_item]*values[i_item] + knapasck_problem_rec(max_weight-weights[i_item], changed_availability, weights, values);

			if (cur_revenue > max_revenue)
			{
				max_revenue = cur_revenue;
				can_put_something = true;
			}
		}
	}

	if (can_put_something)
		return max_revenue;
	else
		return 0;
}

double knapasck_problem(int max_weight, const vector<int> &weights, const vector<int> &values)
{
	vector<bool> available_items(weights.size(), 1);
	return knapasck_problem_rec(max_weight, available_items, weights, values);
}

void main()
{
	int n_items,
		knapasck_weight;
	vector<int> weights,
		values;

	cout << "Input knapsack weight:" << endl;
	cin >> knapasck_weight;

	cout << "Input number of items:" << endl;
	cin >> n_items;

	weights.resize(n_items);
	values.resize(n_items);
	cout << "Input items weights:" << endl;
	for (int i = 0; i < n_items; ++i)
		cin >> weights[i];
	cout << "Input items values:" << endl;
	for (int i = 0; i < n_items; ++i)
		cin >> values[i];

	cout << "maximal possible value = " << knapasck_problem(knapasck_weight, weights, values) << endl;
	_getch();
}